package nowcoder;

public class JudgeSubTree {

	public static void main(String[] args) {
		TreeNode root1 = new TreeNode(8);
		TreeNode node1 = new TreeNode(8);
		TreeNode node2 = new TreeNode(7);
		TreeNode node3 = new TreeNode(9);
		TreeNode node4 = new TreeNode(3);
		TreeNode node5 = new TreeNode(4);
		TreeNode node6 = new TreeNode(7);
		root1.left = node1;
		root1.right = node2;
		node1.left = node3;
		node1.right = node4;
		node2.left = node5;
		node2.right = node6;

		TreeNode root2 = new TreeNode(8);
		TreeNode node21 = new TreeNode(9);
		TreeNode node22 = new TreeNode(2);
		root2.left = node21;
		root2.right = node22;

		System.out.println(isSubtree(root1,root2));
	}

	public static boolean isSubtree(TreeNode root1,TreeNode root2) {
		if(root1 == null || root2 == null)
			return false;
		return isSubtreeFromBegin(root1, root2) ||
				isSubtree(root1.left, root2) ||
				isSubtree(root1.right, root2);
	}

	private static boolean isSubtreeFromBegin(TreeNode begin, TreeNode root2) {
		if(root2 == null)
			return true;
		if(begin == null)
			return false;
		if(begin.val == root2.val) {
			return isSubtreeFromBegin(begin.left, root2.left) & isSubtreeFromBegin(begin.right, root2.right);
		}else {
			return false;
		}
	}

}
